|
In graph theory, a strong coloring, with respect to a partition of the vertices into (disjoint) subsets of equal sizes, is a (proper) vertex coloring in which every color appears exactly once in every partition. When the order of the graph ''G'' is not divisible by ''k'', we add isolated vertices to ''G'' just enough to make the order of the new graph ''G′'' divisible by ''k''. In that case, a strong coloring of ''G′'' minus the previously added isolated vertices is considered a strong coloring of ''G''. A graph is strongly ''k''-colorable if, for each partition of the vertices into sets of size ''k'', it admits a strong coloring. The strong chromatic number sχ(''G'') of a graph ''G'' is the least ''k'' such that ''G'' is strongly ''k''-colorable. A graph is strongly ''k''-chromatic if it has strong chromatic number ''k''. Some properties of sχ(''G''): # sχ(''G'') > Δ(''G''). # sχ(''G'') ≤ 3 Δ(''G'') − 1 (Haxell) # Asymptotically, sχ(''G'') ≤ 11 Δ(''G'') / 4 + o(Δ(''G'')). (Haxell) Here Δ(''G'') is the maximum degree. Strong chromatic number was independently introduced by Alon (1988) and Fellows (1990). == References == * * * * * Jensen, Tommy R.; Toft, Bjarne (1995). ''Graph coloring problems''. New York: Wiley-Interscience. ISBN 0-471-02865-7. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Strong coloring」の詳細全文を読む スポンサード リンク
|